package src.leetcode.backtrack.hard_0332;

import java.util.*;

public class findItinerary {
    public static void main(String[] args) {
        Solution s = new Solution();
        List<List<String>> tickets = new ArrayList<>();
        tickets.add(new ArrayList<>(List.of("JFK", "LHA")));
        tickets.add(new ArrayList<>(List.of("LHA", "LHB")));
        tickets.add(new ArrayList<>(List.of("LHB", "LHC")));
        tickets.add(new ArrayList<>(List.of("LHA", "LHD")));
        tickets.add(new ArrayList<>(List.of("LHD", "LHA")));
        System.out.println(s.findItinerary(tickets)); // ["JFK", "MUC", "LHR", "SFO", "SJC"]
    }
}


class Solution {
    List<String> res = new ArrayList<>();
    HashMap<String, PriorityQueue<String>> map = new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for(List<String> ticket : tickets) {
            if(!map.containsKey(ticket.get(0))) {
                map.put(ticket.get(0), new PriorityQueue<>());
            }
            map.get(ticket.get(0)).offer(ticket.get(1));
        }

        dfs("JFK");
        Collections.reverse(res);
        return res;
    }


    private void dfs(String start){
        while (map.containsKey(start) && map.get(start).size() > 0) {
            String tmp = map.get(start).poll();
            dfs(tmp);
        }
        res.add(start);
    }
}